package com.captain.special.二叉树.中等;

import java.util.HashMap;
import java.util.Map;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/5/14 11:28
 */
public class 不同的二叉搜索树96 {

    Map<Integer, Integer> memo = new HashMap<>();

    public int numTrees(int n) {
        //搜索二叉树的性质: 左节点值 < 中间节点值 < 右边节点值
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int l = lrNumTrees(i - 1);
            int r = lrNumTrees(n - i);
            ans = ans + (l * r);
        }
        return ans;
    }

    /**
     * des:
     * 根据左节点或者右节点的个数 获取延伸的二叉搜索树
     * @param n 左节点或者右节点的个数
     * @author captain
     */
    public int lrNumTrees(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        int count = 0;
        for (int i = 1; i <= n; i++) {
            int leftNum = lrNumTrees(i - 1);
            int rightNum = lrNumTrees(n - i);
            count = count + leftNum * rightNum;
        }
        memo.put(n, count);
        return count;
    }
}
